from collections import defaultdict
